Preface

The origin of the name “Napkin” comes from the following quote of mine.

I’ll be eating a quick lunch with some friends of mine who are still in high school. They’ll ask me what I’ve been up to the last few weeks, and I’ll tell them that I’ve been learning category theory. They’ll ask me what category theory is about. I tell them it’s about abstracting things by looking at just the structure-preserving morphisms between them, rather than the objects themselves. I’ll try to give them the standard example Grp, but then I’ll realize that they don’t know what a homomorphism is. So then I’ll start trying to explain what a homomorphism is, but then I’ll remember that they haven’t learned what a group is. So then I’ll start trying to explain what a group is, but by the time I finish writing the group axioms on my napkin, they’ve already forgotten why I was talking about groups in the first place. And then it’s 1PM, people need to go places, and I can’t help but think:
“Man, if I had forty hours instead of forty minutes, I bet I could actually have explained this all”.

This book was initially my attempt at those forty hours, but has grown considerably since then.

About this book

The Infinitely Large Napkin is a light but mostly self-contained introduction to a large amount of higher math.

I should say at once that this book is not intended as a replacement for dedicated books or courses; the amount of depth is not comparable. On the flip side, the benefit of this “light” approach is that it becomes accessible to a larger audience, since the goal is merely to give the reader a feeling for any particular topic rather than to emulate a full semester of lectures.

I initially wrote this book with talented high-school students in mind, particularly those with math-olympiad type backgrounds. Some remnants of that cultural bias can still be felt throughout the book, particularly in assorted challenge problems which are taken from mathematical competitions. However, in general I think this would be a good reference for anyone with some amount of mathematical maturity and curiosity. Examples include but certainly not limited to: math undergraduate majors, physics/CS majors, math PhD students who want to hear a little bit about fields other than their own, advanced high schoolers who like math but not math contests, and unusually intelligent kittens fluent in English.

Source code

The project is hosted on GitHub at https://github.com/vEnhance/napkin. Pull requests are quite welcome! I am also happy to receive suggestions and corrections by email.

Philosophy behind the Napkin approach

As far as I can tell, higher math for high-school students comes in two flavors:

• Someone tells you about the hairy ball theorem in the form “you can’t comb the hair on a spherical cat” then doesn’t tell you anything about why it should be true, what it means to actually “comb the hair”, or any of the underlying theory, leaving you with just some vague notion in your head.
• You take a class and prove every result in full detail, and at some point you stop caring about what the professor is saying.

Presumably you already know how unsatisfying the first approach is. So the second approach seems to be the default, but I really think there should be some sort of middle ground here.

Unlike university, it is not the purpose of this book to train you to solve exercises or write proofs¹ , or prepare you for research in the field. Instead I just want to show you some interesting math. The things that are presented should be memorable and worth caring about. For that reason, proofs that would be included for completeness in any ordinary textbook are often omitted here, unless there is some idea in the proof which I think is worth seeing. In particular, I place a strong emphasis over explaining why a theorem should be true rather than writing down its proof. This is a recurrent theme of this book:

My hope is that after reading any particular chapter in Napkin, one might get the following out of it:

• Knowing what the precise definitions are of the main characters,
• Being acquainted with the few really major examples,
• Knowing the precise statements of famous theorems, and having a sense of why they should be true.

Understanding “why” something is true can have many forms. This is sometimes accomplished with a complete rigorous proof; in other cases, it is given by the idea of the proof; in still other cases, it is just a few key examples with extensive cheerleading.

Obviously this is nowhere near enough if you want to e.g. do research in a field; but if you are just a curious outsider, I hope that it’s more satisfying than the elevator pitch or Wikipedia articles. Even if you do want to learn a topic with serious depth, I hope that it can be a good zoomed-out overview before you really dive in, because in many senses the choice of material is “what I wish someone had told me before I started”.

More pedagogical comments and references

The preface would become too long if I talked about some of my pedagogical decisions chapter by chapter, so ??  contains those comments instead.

In particular, I often name specific references, and the end of that appendix has more references. So this is a good place to look if you want further reading.

Historical and personal notes

I began writing this book in December of 2014, after having finished my first semester of undergraduate at Harvard. It became my main focus for about 18 months after that, as I became immersed in higher math. I essentially took only math classes, (gleefully ignoring all my other graduation requirements) and merged as much of it as I could (as well as lots of other math I learned on my own time) into the Napkin.

Towards August of 2016, though, I finally lost steam. The first public drafts went online then, and I decided to step back. Having burnt out slightly, I then took a break from higher math, and spent the remaining two undergraduate years² working extensively as a coach for the American math olympiad team, and trying to spend as much time with my friends as I could before they graduated and went their own ways.

During those two years, readers sent me many kind words of gratitude, many reports of errors, and many suggestions for additions. So in November of 2018, some weeks into my first semester as a math PhD student, I decided I should finish what I had started. Some months later, here is what I have.

Acknowledgements

I am indebted to countless people for this work. Here is a partial (surely incomplete) list.

• Thanks to all my teachers and professors for teaching me much of the material covered in these notes, as well as the authors of all the references I have cited here. A special call-out to [?], [?], [?], [?], [?], [?], [?], [?], [?], [?], which were especially influential.
• Thanks also to dozens of friends and strangers who read through preview copies of my draft, and pointed out errors and gave other suggestions. Special mention to Andrej Vuković and Alexander Chua for together catching over a thousand errors. Thanks also to Brian Gu and Tom Tseng for many corrections. (If you find mistakes or have suggestions yourself, I would love to hear them!)
• I’d also like to express my gratitude for many, many kind words I received during the development of this project. These generous comments led me to keep working on this, and were largely responsible for my decision in November 2018 to begin updating the Napkin again.

Finally, a huge thanks to the math olympiad community, from which the Napkin (and me) has its roots. All the enthusiasm, encouragement, and thank-you notes I have received over the years led me to begin writing this in the first place. I otherwise would never have the arrogance to dream a project like this was at all possible. And of course I would be nowhere near where I am today were it not for the life-changing journey I took in chasing my dreams to the IMO. Forever TWN2!

Advice for the reader

1  Prerequisites

As explained in the preface, the main prerequisite is some amount of mathematical maturity. This means I expect the reader to know how to read and write a proof, follow logical arguments, and so on.

I also assume the reader is familiar with basic terminology about sets and functions (e.g. “what is a bijection?”). If not, one should consult ?? .

2  Deciding what to read

There is no need to read this book in linear order: it covers all sorts of areas in mathematics, and there are many paths you can take. In ?? , I give a short overview for each part explaining what you might expect to see in that part.

For now, here is a brief chart showing how the chapters depend on each other; again see ??  for details. Dependencies are indicated by arrows; dotted lines are optional dependencies. I suggest that you simply pick a chapter you find interesting, and then find the shortest path. With that in mind, I hope the length of the entire PDF is not intimidating.

3  Questions, exercises, and problems

In this book, there are three hierarchies:

• An inline question is intended to be offensively easy, mostly a chance to help you internalize definitions. If you find yourself unable to answer one or two of them, it probably means I explained it badly and you should complain to me. But if you can’t answer many, you likely missed something important: read back.
• An inline exercise is more meaty than a question, but shouldn’t have any “tricky” steps. Often I leave proofs of theorems and propositions as exercises if they are instructive and at least somewhat interesting.
• Each chapter features several trickier problems at the end. Some are reasonable, but others are legitimately difficult olympiad-style problems.       Harder problems are marked with up to three chili peppers ( ), like this paragraph.

  In addition to difficulty annotations, the problems are also marked by how important they are to the big picture.

  • Normal problems, which are hopefully fun but non-central.
  • Daggered problems, which are (usually interesting) results that one should know, but won’t be used directly later.
  • Starred problems, which are results which will be used later on in the book.¹

Several hints and solutions can be found in ?? .

4  Paper

At the risk of being blunt,

Here’s why:

You are not God. You cannot keep everything in your head.² If you’ve printed out a hard copy, then write in the margins. If you’re trying to save paper, grab a notebook or something along with the ride. Somehow, some way, make sure you can write. Thanks.

5  On the importance of examples

I am pathologically obsessed with examples. In this book, I place all examples in large boxes to draw emphasis to them, which leads to some pages of the book simply consisting of sequences of boxes one after another. I hope the reader doesn’t mind.

I also often highlight a “prototypical example” for some sections, and reserve the color red for such a note. The philosophy is that any time the reader sees a definition or a theorem about such an object, they should test it against the prototypical example. If the example is a good prototype, it should be immediately clear why this definition is intuitive, or why the theorem should be true, or why the theorem is interesting, et cetera.

Let me tell you a secret. Whenever I wrote a definition or a theorem in this book, I would have to recall the exact statement from my (quite poor) memory. So instead I often consider the prototypical example, and then only after that do I remember what the definition or the theorem is. Incidentally, this is also how I learned all the definitions in the first place. I hope you’ll find it useful as well.

6  Conventions and notations

This part describes some of the less familiar notations and definitions and settles for once and for all some annoying issues (“is zero a natural number?”). Most of these are “remarks for experts”: if something doesn’t make sense, you probably don’t have to worry about it for now.

A full glossary of notation used can be found in the appendix.

6.i  Natural numbers are positive

The set ℕ is the set of positive integers, not including 0. In the set theory chapters, we use ω = {0,1,…} instead, for consistency with the rest of the book.

6.ii  Sets and equivalence relations

This is brief, intended as a reminder for experts. Consult ??  for full details.

An equivalence relation on a set X is a relation ∼ which is symmetric, reflexive, and transitive. An equivalence relation partitions X into several equivalence classes. We will denote this by X∕∼. An element of such an equivalence class is a representative of that equivalence class.

I always use for an “isomorphism”-style relation (formally: a relation which is an isomorphism in a reasonable category). The only time ≃ is used in the Napkin is for homotopic paths.

I generally use ⊆ and ⊊ since these are non-ambiguous, unlike ⊂. I only use ⊂ on rare occasions in which equality obviously does not hold yet pointing it out would be distracting. For example, I write ℚ ⊂ ℝ since “ℚ ⊊ ℝ” is distracting.

I prefer S ∖ T to S − T.

The power set of S (i.e., the set of subsets of S), is denoted either by 2^S or 𝒫(S).

6.iii  Functions

This is brief, intended as a reminder for experts. Consult ??  for full details.

Let XY be a function:

• By fpre(T) I mean the pre-image
  

  This is in contrast to the f−1(T) used in the rest of the world; I only use f−1 for an inverse function.

  By abuse of notation, we may abbreviate fpre({y}) to fpre(y). We call fpre(y) a fiber.

• By fimg(S) I mean the image
  

  Almost everyone else in the world uses f(S) (though f[S] sees some use, and f“(S) is often used in logic) but this is abuse of notation, and I prefer fimg(S) for emphasis. This image notation is not standard.

• If S ⊆ X, then the restriction of f to S is denoted f↾S, i.e. it is the function f↾S : S → Y .
• Sometimes functions f : X → Y are injective or surjective; I may emphasize this sometimes by writing f : XY or f : X ↠ Y , respectively.

6.iv  Cycle notation for permutations

Additionally, a permutation on a finite set may be denoted in cycle notation, as described in say https://en.wikipedia.org/wiki/Permutation#Cycle_notation. For example the notation (1 2 3 4)(5 6 7) refers to the permutation with 12, 23, 34, 41, 56, 67, 75. Usage of this notation will usually be obvious from context.

6.v  Rings

All rings have a multiplicative identity 1 unless otherwise specified. We allow 0 = 1 in general rings but not in integral domains.

All rings are commutative unless otherwise specified. There is an elaborate scheme for naming rings which are not commutative, used only in the chapter on cohomology rings:

On the other hand, an algebra always has 1, but it need not be commutative.

6.vi  Choice

We accept the Axiom of Choice, and use it freely.

7  Further reading

The appendix ??  contains a list of resources I like, and explanations of pedagogical choices that I made for each chapter. I encourage you to check it out.

In particular, this is where you should go for further reading! There are some topics that should be covered in the Napkin, but are not, due to my own ignorance or laziness. The references provided in this appendix should hopefully help partially atone for my omissions.

Contents

Part I
Starting Out

0  Sales pitches

This chapter contains a pitch for each part, to help you decide what you want to read and to elaborate more on how they are interconnected.

For convenience, here is again the dependency plot that appeared in the frontmatter.

0.1  The basics

• Starting Out.
  I made a design decision that the first part should have a little bit both of algebra and topology: so this first chapter begins by defining a group, while the second chapter begins by defining a metric space. The intention is so that newcomers get to see two different examples of “sets with additional structure” in somewhat different contexts, and to have a minimal amount of literacy as these sorts of definitions appear over and over.¹
• Basic Abstract Algebra.
  The algebraically inclined can then delve into further types of algebraic structures: some more details of groups, and then rings and fields — which will let you generalize ℤ, ℚ, ℝ, ℂ. So you’ll learn to become familiar with all sorts of other nouns that appear in algebra, unlocking a whole host of objects that one couldn’t talk about before.

  We’ll also come into ideals, which generalize the GCD in ℤ that you might know of. For example, you know in ℤ that any integer can be written in the form 3a+5b for a,b ∈ ℤ, since gcd(3,5) = 1. We’ll see that this statement is really a statement of ideals: “(3,5) = 1 in ℤ”, and thus we’ll understand in what situations it can be generalized, e.g. to polynomials.

• Basic Topology.
  The more analytically inclined can instead move into topology, learning more about spaces. We’ll find out that “metric spaces” are actually too specific, and that it’s better to work with topological spaces, which are based on the so-called open sets. You’ll then get to see the buddings of some geometrical ideals, ending with the really great notion of compactness, a powerful notion that makes real analysis tick.

  One example of an application of compactness to tempt you now: a continuous function f : [0,1] → ℝ always achieves a maximum value. (In contrast, f : (0,1) → ℝ by x1∕x does not.) We’ll see the reason is that [0,1] is compact.

0.2  Abstract algebra

• Linear Algebra.
  In high school, linear algebra is often really unsatisfying. You are given these arrays of numbers, and they’re manipulated in some ways that don’t really make sense. For example, the determinant is defined as this funny-looking sum with a bunch of products that seems to come out of thin air. Where does it come from? Why does det(AB) = detAdetB with such a bizarre formula?

  Well, it turns out that you can explain all of these things! The trick is to not think of linear algebra as the study of matrices, but instead as the study of linear maps. In earlier chapters we saw that we got great generalizations by speaking of “sets with enriched structure” and “maps between them”. This time, our sets are vector spaces and our maps are linear maps. We’ll find out that a matrix is actually just a way of writing down a linear map as an array of numbers, but using the “intrinsic” definitions we’ll de-mystify all the strange formulas from high school and show you where they all come from.

  In particular, we’ll see easy proofs that column rank equals row rank, determinant is multiplicative, trace is the sum of the diagonal entries. We’ll see how the dot product works, and learn all the words starting with “eigen-”. We’ll even have a bonus chapter for Fourier analysis showing that you can also explain all the big buzz-words by just being comfortable with vector spaces.

• More on Groups.
  Some of you might be interested in more about groups, and this chapter will give you a way to play further. It starts with an exploration of group actions, then goes into a bit on Sylow theorems, which are the tools that let us try to classify all groups.
• Representation Theory.
  If G is a group, we can try to understand it by implementing it as a matrix, i.e. considering embeddings GGL_n(ℂ). These are called representations of G; it turns out that they can be decomposed into irreducible ones. Astonishingly we will find that we can basically characterize all of them: the results turn out to be short and completely unexpected.

  For example, we will find out that there are finitely many irreducible representations of a given finite group G; if we label them V ₁, V ₂, …, V _r, then we will find that r is the number of conjugacy classes of G, and moreover that

  

  which comes out of nowhere!

  The last chapter of this part will show you some unexpected corollaries. Here is one of them: let G be a finite group and create variables x_g for each g ∈ G. A |G|×|G| matrix M is defined by setting the (g,h)th entry to be the variable x_g⋅h. Then this determinant will turn out to factor, and the factors will correspond to the V _i we described above: there will be an irreducible factor of degree dimV _i appearing dimV _i times. This result, called the Frobenius determinant, is said to have given birth to representation theory.

• Quantum Algorithms.
  If you ever wondered what Shor’s algorithm is, this chapter will use the built-up linear algebra to tell you!

0.3  Real and complex analysis

• Calculus 101.
  In this part, we’ll use our built-up knowledge of metric and topological spaces to give short, rigorous definitions and theorems typical of high school calculus. That is, we’ll really define and prove most everything you’ve seen about limits, series, derivatives, and integrals.

  Although this might seem intimidating, it turns out that actually, by the time we start this chapter, the hard work has already been done: the notion of limits, open sets, and compactness will make short work of what was swept under the rug in AP calculus. Most of the proofs will thus actually be quite short. We sit back and watch all the pieces slowly come together as a reward for our careful study of topology beforehand.

  That said, if you are willing to suspend belief, you can actually read most of the other parts without knowing the exact details of all the calculus here, so in some sense this part is “optional”.

• Complex Analysis.
  It turns out that holomorphic functions (complex-differentiable functions) are close to the nicest things ever: they turn out to be given by a Taylor series (i.e. are basically polynomials). This means we’ll be able to prove unreasonably nice results about holomorphic functions ℂ → ℂ, like
  • they are determined by just a few inputs,
  • their contour integrals are all zero,
  • they can’t be bounded unless they are constant,
  • ….

  We then introduce meromorphic functions, which are like quotients of holomorphic functions, and find that we can detect their zeros by simply drawing loops in the plane and integrating over them: the famous residue theorem appears. (In the practice problems, you will see this even gives us a way to evaluate real integrals that can’t be evaluated otherwise.)

• Measure Theory.
  Measure theory is the upgraded version of integration. The Riemann integration is for a lot of purposes not really sufficient; for example, if f is the function equals 1 at rational numbers but 0 at irrational numbers, we would hope that ∫ ₀¹f(x) dx = 0, but the Riemann integral is not capable of handling this function f.

  The Lebesgue integral will handle these mistakes by assigning a measure to a generic space Ω, making it into a measure space. This will let us develop a richer theory of integration where the above integral does work out to zero because the “rational numbers have measure zero”. Even the development of the measure will be an achievement, because it means we’ve developed a rigorous, complete way of talking about what notions like area and volume mean — on any space, not just ℝⁿ! So for example the Lebesgue integral will let us integrate functions over any measure space.

• Probability (TO DO).
  Using the tools of measure theory, we’ll be able to start giving rigorous definitions of probability, too. We’ll see that a random variable is actually a function from a measure space of worlds to ℝ, giving us a rigorous way to talk about its probabilities. We can then start actually stating results like the law of large numbers and central limit theorem in ways that make them both easy to state and straightforward to prove.
• Differential Geometry.
  Multivariable calculus is often confusing because of all the partial derivatives. But we’ll find out that, armed with our good understanding of linear algebra, that we’re really looking at a total derivative: at every point of a function f : ℝⁿ → ℝ we can associate a linear map Df which captures in one object the notion of partial derivatives. Set up this way, we’ll get to see versions of differential forms and Stokes’ theorem, and we finally will know what the notation dx really means. In the end, we’ll say a little bit about manifolds in general.

0.4  Algebraic number theory

• Algebraic NT I: Rings of Integers.
  Why is 3+ the conjugate of 3−? How come the norm = a²−5b² used in Pell equations just happens to be multiplicative? Why is it we can do factoring into primes in ℤ[i] but not in ℤ[]? All these questions and more will be answered in this part, when we learn about number fields, a generalization of ℚ and ℤ to things like ℚ() and ℤ[]. We’ll find out that we have unique factorization into prime ideals, that there is a real multiplicative norm in play here, and so on. We’ll also see that Pell’s equation falls out of this theory.
• Algebraic NT II: Galois and Ramification Theory.
  All the big buzz-words come out now: Galois groups, the Frobenius, and friends. We’ll see quadratic reciprocity is just a shadow of the behavior of the Frobenius element, and meet the Chebotarev density theorem, which generalizes greatly the Dirichlet theorem on the infinitude of primes which are a (mod n). Towards the end, we’ll also state Artin reciprocity, one of the great results of class field theory, and how it generalizes quadratic reciprocity and cubic reciprocity.

0.5  Algebraic topology

• Algebraic Topology I: Homotopy.
  What’s the difference between an annulus and disk? Well, one of them has a “hole” in it, but if we are just given intrinsic topological spaces it’s hard to make this notion precise. The fundamental group π₁(X) and more general homotopy group will make this precise — we’ll find a way to define an abelian group π₁(X) for every topological space X which captures the idea there is a hole in the space, by throwing lassos into the space and seeing if we can reel them in.

  Amazingly, the fundamental group π₁(X) will, under mild conditions, tell you about ways to cover X with a so-called covering projection. One picture is that one can wrap a real line ℝ into a helix shape and then project it down into the circle S¹. This will turn out to correspond to the fact that π₁(S¹) = ℤ which has only one subgroup. More generally the subgroups of π₁(X) will be in bijection with ways to cover the space X!

• Category Theory.
  What do fields, groups, manifolds, metric spaces, measure spaces, modules, representations, rings, topological spaces, vector spaces, all have in common? Answer: they are all “objects with additional structure”, with maps between them.

  The notion of category will appropriately generalize all of them. We’ll see that all sorts of constructions and ideas can be abstracted into the framework of a category, in which we only think about objects and arrows between them, without probing too hard into the details of what those objects are. This results in drawing many commutative diagrams.

  For example, any way of taking an object in one category and getting another one (for example π₁ as above, from the category of spaces into the category of groups) will probably be a functor. We’ll unify G×H, X ×Y , R ×S, and anything with the × symbol into the notion of a product, and then even more generally into a limit. Towards the end, we talk about abelian categories and talk about the famous snake lemma, five lemma, and so on.

• Algebraic Topology II: Homology.
  Using the language of category theory, we then resume our adventures in algebraic topology, in which we define the homology groups which give a different way of noticing holes in a space, in a way that is longer to define but easier to compute in practice. We’ll then reverse the construction to get so-called cohomology rings instead, which give us an even finer invariant for telling spaces apart.

0.6  Algebraic geometry

• Algebraic Geometry I: Classical Varieties.
  We begin with a classical study of classical complex varieties: the study of intersections of polynomial equations over ℂ. This will naturally lead us into the geometry of rings, giving ways to draw pictures of ideals, and motivating Hilbert’s nullstellensatz. The Zariski topology will show its face, and then we’ll play with projective varities and quasi-projective varieties, with a bonus detour into Bezout’s theorem. All this prepares us for our journey into schemes.
• Algebraic Geometry II: Affine Schemes.
  We now get serious and delve into Grothendiek’s definition of an affine scheme: a generalization of our classical varieties that lets us start with any ring A and construct a space SpecA on it. We’ll equip it with its own Zariski topology and then a sheaf of functions on it, making it into a locally ringed space; we will find that the sheaf can be understood effectively in terms of localization on it. We’ll find that the language of commutative algebra provides elegant generalizations of what’s going on geometrically: prime ideals correspond to irreducible closed subsets, radical ideals correspond to closed subsets, maximal ideals correspond to closed points, and so on. We’ll draw lots of pictures of spaces and examples to accompany this.
• Algebraic Geometry III: Schemes (TO DO).
  Not yet written! Wait for v2.

0.7  Set theory

• Set Theory I: ZFC, Ordinals, and Cardinals.
  Why is Russell’s paradox such a big deal and how is it resolved? What is this Zorn’s lemma that everyone keeps talking about? In this part we’ll learn the answers to these questions by giving a real description of the Zermelo-Frankel axioms, and the axiom of choice, delving into the details of how math is built axiomatically at the very bottom foundations. We’ll meet the ordinal numbers and cardinal numbers and learn how to do transfinite induction with them.
• Set Theory II: Model Theory and Forcing.
  The continuum hypothesis states that there are no cardinalities between the size of the natural numbers and the size of the real numbers. It was shown to be independent of the axioms — one cannot prove or disprove it. How could a result like that possibly be proved? Using our understanding of the ZF axioms, we’ll develop a bit of model theory and then use forcing in order to show how to construct entire models of the universe in which the continuum hypothesis is true or false.

1  Groups

A group is one of the most basic structures in higher mathematics. In this chapter I will tell you only the bare minimum: what a group is, and when two groups are the same.

1.1  Definition and examples of groups

Prototypical example for this section: The additive group of integers (ℤ,+) and the cyclic group ℤ∕mℤ. Just don’t let yourself forget that most groups are non-commutative.

A group consists of two pieces of data: a set G, and an associative binary operation ⋆ with some properties. Before I write down the definition of a group, let me give two examples.

From this you might already have a guess what the definition of a group is.

Let’s resume writing down examples. Here are some more abelian examples of groups:

Example 1.1.7 (Complex unit circle)
Let S¹ denote the set of complex numbers z with absolute value one; that is

Then (S¹,×) is a group because

• The complex number 1 ∈ S¹ serves as the identity, and
• Each complex number z ∈ S¹ has an inverse which is also in S¹, since = −1 = 1.

There is one thing I ought to also check: that z₁ × z₂ is actually still in S¹. But this follows from the fact that = = 1.

(Digression: the notation ℤ∕nℤ and (ℤ∕pℤ)× may seem strange but will make sense when we talk about rings and ideals. Set aside your worry for now.)

Here are some non-abelian examples:

Example 1.1.14 (Dihedral group)
The dihedral group of order 2n, denoted D_2n, is the group of symmetries of a regular n-gon A₁A₂…A_n, which includes rotations and reflections. It consists of the 2n elements

The element r corresponds to rotating the n-gon by , while s corresponds to reflecting it across the line OA₁ (here O is the center of the polygon). So rs mean “reflect then rotate” (like with function composition, we read from right to left).

In particular, rⁿ = s² = 1. You can also see that r^ks = sr^−k.

Here is a picture of some elements of D₁₀.

Trivia: the dihedral group D₁₂ is my favorite example of a non-abelian group, and is the first group I try for any exam question of the form “find an example…”.

More examples:

Example 1.1.15 (Products of groups)
Let (G,⋆) and (H,∗) be groups. We can define a product group (G × H,⋅), as follows. The elements of the group will be ordered pairs (g,h) ∈ G × H. Then

is the group operation.

1.2  Properties of groups

Prototypical example for this section: (ℤ∕pℤ)× is possibly best.

Abuse of Notation 1.2.2. From now on, for any g ∈ G and n ∈ ℕ we abbreviate

Moreover, we let g−1 denote the inverse of g, and g⁻ⁿ = (g−1)ⁿ.

In mathematics, a common theme is to require that objects satisfy certain minimalistic properties, with certain examples in mind, but then ignore the examples on paper and try to deduce as much as you can just from the properties alone. (Math olympiad veterans are likely familiar with “functional equations” in which knowing a single property about a function is enough to determine the entire function.) Let’s try to do this here, and see what we can conclude just from knowing ?? .

It is a law in Guam and 37 other states that I now state the following proposition.

Now we state a slightly more useful proposition.

Proof. Direct computation. We have

Hence (ab)−1 = b−1a−1. Similarly, (b−1a−1)(ab) = 1_G as well. □

Finally, we state a very important lemma about groups, which highlights why having an inverse is so valuable.

Example 1.2.7
Let G = (ℤ∕7ℤ)× (as in ?? ) and pick g = 3. The above lemma states that the map x3 ⋅ x is a bijection, and we can see this explicitly:

1	3 (mod 7)
2	6 (mod 7)
3	2 (mod 7)
4	5 (mod 7)
5	1 (mod 7)
6	4 (mod 7).

The fact that the map is injective is often called the cancellation law. (Why do you think so?)

1.3  Isomorphisms

Prototypical example for this section: ℤ10ℤ.

First, let me talk about what it means for groups to be isomorphic. Consider the two groups

• ℤ = (,+).
• 10ℤ = (,+).

These groups are “different”, but only superficially so – you might even say they only differ in the names of the elements. Think about what this might mean formally for a moment.

Specifically the map

is a bijection of the underlying sets which respects the group action. In symbols,

In other words, ϕ is a way of re-assigning names of the elements without changing the structure of the group. That’s all just formalism for capturing the obvious fact that (ℤ,+) and (10ℤ,+) are the same thing.

Now, let’s do the general definition.

Definition 1.3.1. Let G = (G,⋆) and H = (H,∗) be groups. A bijection ϕ : G → H is called an isomorphism if

If there exists an isomorphism from G to H, then we say G and H are isomorphic and write GH.

Note that in this definition, the left-hand side ϕ(g₁ ⋆ g₂) uses the operation of G while the right-hand side ϕ(g₁) ∗ ϕ(g₂) uses the operation of H.

Example 1.3.3 (Primitive roots modulo 7)
As a nontrivial example, we claim that ℤ∕6ℤ(ℤ∕7ℤ)×. The bijection is

To check that this is an isomorphism, we need to verify several things.

• First, we need to check this map actually makes sense: why is it the case that if a ≡ b (mod 6), then 3^a ≡ 3^b (mod 7)? The reason is that Fermat’s little theorem guarantees that 3⁶ ≡ 1 (mod 7).
• Next, we need to check that this map is a bijection. You can do this explicitly:
  
• Finally, we need to verify that this map respects the group action. In other words, we want to see that ϕ(a+b) = ϕ(a)ϕ(b) since the operation of ℤ∕6ℤ is addition while the operation of (ℤ∕7ℤ)× is multiplication. That’s just saying that 3^a+b ≡ 3^a3^b (mod 7), which is true.

Example 1.3.4 (Primitive roots)
More generally, for any prime p, there exists an element g ∈ (ℤ∕pℤ)× called a primitive root modulo p such that 1,g,g²,…,g^p−2 are all different modulo p. One can show by copying the above proof that

The example above was the special case p = 7 and g = 3.

It’s not hard to see that is an equivalence relation (why?). Moreover, because we really only care about the structure of groups, we’ll usually consider two groups to be the same when they are isomorphic. So phrases such as “find all groups” really mean “find all groups up to isomorphism”.

1.4  Orders of groups, and Lagrange’s theorem

Prototypical example for this section: (ℤ∕pℤ)×.

As is typical in math, we use the word “order” for way too many things. In groups, there are two notions of order.

You might also know that if xⁿ ≡ 1 (mod p), then the order of x (mod p) must divide n. The same is true in a general group for exactly the same reason.

Also, you can show that any element of a finite group has a finite order. The proof is just an olympiad-style pigeonhole argument. Consider the infinite sequence 1_G,g,g²,…, and find two elements that are the same.

What’s the last property of (ℤ∕pℤ)× that you know from olympiad math? We have Fermat’s little theorem: for any a ∈ (ℤ∕pℤ)×, we have a^p−1 ≡ 1 (mod p). This is no coincidence: exactly the same thing is true in a more general setting.

Keep this result in mind! We’ll prove it later in the generality of ?? .

1.5  Subgroups

Prototypical example for this section: SL_n(ℝ) is a subgroup of GL_n(ℝ).

Earlier we saw that GL_n(ℝ), the n×n matrices with nonzero determinant, formed a group under matrix multiplication. But we also saw that a subset of GL_n(ℝ), namely SL_n(ℝ), also formed a group with the same operation. For that reason we say that SL_n(ℝ) is a subgroup of GL_n(ℝ). And this definition generalizes in exactly the way you expect.

Next is an especially important example that we’ll talk about more in later chapters.

Example 1.5.5 (Subgroup generated by an element)
Let x be an element of a group G. Consider the set

This is also a subgroup of G, called the subgroup generated by x.

Finally, we present some non-examples of subgroups.

1.6  Groups of small orders

Just for fun, here is a list of all groups of order less than or equal to ten (up to isomorphism, of course).

1.

The only group of order 1 is the trivial group.

2.

The only group of order 2 is ℤ∕2ℤ.

3.

The only group of order 3 is ℤ∕3ℤ.

4.

The only groups of order 4 are

• ℤ∕4ℤ, the cyclic group on four elements,
• ℤ∕2ℤ × ℤ∕2ℤ, called the Klein Four Group.

5.

The only group of order 5 is ℤ∕5ℤ.

6.

The groups of order six are

• ℤ∕6ℤ, the cyclic group on six elements.
• S₃, the permutation group of three elements. This is the first non-abelian group.

Some of you might wonder where ℤ∕2ℤ × ℤ∕3ℤ is. All I have to say is: Chinese remainder theorem!

You might wonder where D₆ is in this list. It’s actually isomorphic to S₃.

7.

The only group of order 7 is ℤ∕7ℤ.

8.

The groups of order eight are more numerous.

• ℤ∕8ℤ, the cyclic group on eight elements.
• ℤ∕4ℤ × ℤ∕2ℤ.
• ℤ∕2ℤ × ℤ∕2ℤ × ℤ∕2ℤ.
• D₈, the dihedral group with eight elements, which is not abelian.
• A non-abelian group Q₈, called the quaternion group. It consists of eight elements ±1, ±i, ±j, ±k with i² = j² = k² = ijk = −1.

9.

The groups of order nine are

• ℤ∕9ℤ, the cyclic group on nine elements.
• ℤ∕3ℤ × ℤ∕3ℤ.

10.

The groups of order 10 are

• ℤ∕10ℤℤ∕5ℤ × ℤ∕2ℤ (again Chinese remainder theorem).
• D₁₀, the dihedral group with 10 elements. This group is non-abelian.

1.7  Unimportant long digression

A common question is: why these axioms? For example, why associative but not commutative? This answer will likely not make sense until later, but here are some comments that may help.

One general heuristic is: Whenever you define a new type of general object, there’s always a balancing act going on. On the one hand, you want to include enough constraints that your objects are “nice”. On the other hand, if you include too many constraints, then your definition applies to too few objects.

So, for example, we include “associative” because that makes our lives easier and most operations we run into are associative. In particular, associativity is required for the inverse of an element to necessarily be unique. However we don’t include “commutative”, because examples below show that there are lots of non-abelian groups we care about. (But we introduce another name “abelian” because we still want to keep track of it.)

Another comment: a good motivation for the inverse axioms is that you get a large amount of symmetry. The set of positive integers with addition is not a group, for example, because you can’t subtract 6 from 3: some elements are “larger” than others. By requiring an inverse element to exist, you get rid of this issue. (You also need identity for this; it’s hard to define inverses without it.)

Even more abstruse comment: ??  shows that groups are actually shadows of the so-called symmetric groups (defined later, also called permutation groups). This makes rigorous the notion that “groups are very symmetric”.

1.8  A few harder problems to think about

2  Metric spaces

At the time of writing, I’m convinced that metric topology is the morally correct way to motivate point-set topology as well as to generalize normal calculus.¹ So here is my best attempt.

The concept of a metric space is very “concrete”, and lends itself easily to visualization. Hence throughout this chapter you should draw lots of pictures as you learn about new objects, like convergent sequences, open sets, closed sets, and so on.

2.1  Definition and examples of metric spaces

Prototypical example for this section: ℝ², with the Euclidean metric.

Example 2.1.5 (Taxicab on ℝ²)
It is also possible to place the taxicab distance on ℝ²:

For now, we will use the more natural Euclidean metric.

Here is a slightly more pathological example.

Example 2.1.8 (Discrete space)
Let S be any set of points (either finite or infinite). We can make S into a discrete space by declaring

If = 4 you might think of this space as the vertices of a regular tetrahedron, living in ℝ³. But for larger S it’s not so easy to visualize…

2.2  Convergence in metric spaces

Prototypical example for this section: The sequence (for n = 1,2,…) in ℝ.

Since we can talk about the distance between two points, we can talk about what it means for a sequence of points to converge. This is the same as the typical epsilon-delta definition, with absolute values replaced by the distance function.

Definition 2.2.1. Let (x_n)_n≥1 be a sequence of points in a metric space M. We say that x_n converges to x if the following condition holds: for all 𝜀 > 0, there is an integer N (depending on 𝜀) such that d(x_n,x) < 𝜀 for each n ≥ N. This is written

or more verbosely as

We say that a sequence converges in M if it converges to a point in M.

You should check that this definition coincides with your intuitive notion of “converges”.

2.3  Continuous maps

In calculus you were also told (or have at least heard) of what it means for a function to be continuous. Probably something like

A function f : ℝ → ℝ is continuous at a point p ∈ ℝ if for every 𝜀 > 0 there exists a δ > 0 such that < δ < 𝜀.

All we have do is replace the absolute values with the more general distance functions: this gives us a definition of continuity for any function M → N.

Definition 2.3.2. Let M = (M,d_M) and N = (N,d_N) be metric spaces. A function f : M → N is continuous at a point p ∈ M if for every 𝜀 > 0 there exists a δ > 0 such that

Moreover, the entire function f is continuous if it is continuous at every point p ∈ M.

Notice that, just like in our definition of an isomorphism of a group, we use the metric of M for one condition and the metric of N for the other condition.

This generalization is nice because it tells us immediately how we could carry over continuity arguments in ℝ to more general spaces like ℂ. Nonetheless, this definition is kind of cumbersome to work with, because it makes extensive use of the real numbers (epsilons and deltas). Here is an equivalent condition.

Example application showcasing the niceness of sequential continuity:

2.4  Homeomorphisms

Prototypical example for this section: The unit circle S¹ is homeomorphic to the boundary of the unit square.

When do we consider two groups to be the same? Answer: if there’s a structure-preserving map between them which is also a bijection. For metric spaces, we do exactly the same thing, but replace “structure-preserving” with “continuous”.

Needless to say, homeomorphism is an equivalence relation.

You might be surprised that we require f−1 to also be continuous. Here’s the reason: you can show that if ϕ is an isomorphism of groups, then ϕ−1 also preserves the group operation, hence ϕ−1 is itself an isomorphism. The same is not true for continuous bijections, which is why we need the new condition.

Note that this is the topologist’s definition of “same” – homeomorphisms are “continuous deformations”. Here are some examples.

Example 2.4.5 (Homeomorphisms really don’t preserve size)
Surprisingly, the open interval (−1,1) is homeomorphic to the real line ℝ! One bijection is given by

with the inverse being given by t arctan(t).

This might come as a surprise, since (−1,1) doesn’t look that much like ℝ; the former is “bounded” while the latter is “unbounded”.

2.5  Extended example/definition: product metric

Prototypical example for this section: ℝ × ℝ is ℝ².

Here is an extended example which will occur later on. Let M = (M,d_M) and N = (N,d_N) be metric spaces (say, M = N = ℝ). Our goal is to define a metric space on M × N.

Let p_i = (x_i,y_i) ∈ M × N for i = 1,2. Consider the following metrics on the set of points M × N:

dmax(p1,p2)	: = max
dEuclid(p1,p2)	: =
dtaxicab	:= dM(x1,x2) + dN(y1,y2).

All of these are good candidates. We are about to see it doesn’t matter which one we use:

Exercise 2.5.1. Verify that

Use this to show that the metric spaces we obtain by imposing any of the three metrics are homeomorphic, with the homeomorphism being just the identity map.

The product metric plays well with convergence of sequences.

Let’s see an application of this:

Proof. For multiplication: for any n we have

xnyn	=
	= xy + y(xn − x) + x(yn − y) + (xn − x)(yn − y)
	≤ + + .

As n →∞, all three terms on the right-hand side tend to zero. The proof that +: ℝ × ℝ → ℝ is continuous is similar (and easier): one notes for any n that

and both terms on the right-hand side tend to zero as n →∞. □

??  covers the other two operations, subtraction and division. The upshot of this is that, since compositions are also continuous, most of your naturally arising real-valued functions will automatically be continuous as well. For example, the function will be a continuous function from ℝ → ℝ, since it can be obtained by composing +, ×, ÷.

2.6  Open sets

Prototypical example for this section: The open disk x² + y² < r² in ℝ².

Continuity is really about what happens “locally”: how a function behaves “close to a certain point p”. One way to capture this notion of “closeness” is to use metrics as we’ve done above. In this way we can define an r-neighborhood of a point.

Definition 2.6.1. Let M be a metric space. For each real number r > 0 and point p ∈ M, we define

The set M_r(p) is called an r-neighborhood of p.

We can rephrase convergence more succinctly in terms of r-neighborhoods. Specifically, a sequence (x_n) converges to x if for every r-neighborhood of x, all terms of x_n eventually stay within that r-neighborhood.

Let’s try to do the same with functions.

Essentially, we require that the pre-image of every 𝜀-neighborhood has the property that some δ-neighborhood exists inside it. This motivates:

Here are two quite important properties of open sets.

The whole upshot of this is:

2.7  Closed sets

Prototypical example for this section: The closed unit disk x² + y² ≤ r² in ℝ².

It would be criminal for me to talk about open sets without talking about closed sets. The name “closed” comes from the definition in a metric space.

Here’s another way to phrase it. The limit points of a subset S ⊆ M are defined by

Thus S is closed if and only if S = limS.

For this reason, limS is also called the closure of S in M, and denoted S. It is simply the smallest closed set which contains S.

Example 2.7.5 (Non-examples of closed sets)
Let S = (0,1) denote the open interval. Then S is not closed in ℝ because the sequence of points

converges to 0 ∈ ℝ, but 0(0,1).

I should now warn you about a confusing part of this terminology. Firstly, “most” sets are neither open nor closed.

Secondly, it’s also possible for a set to be both open and closed; this will be discussed in ?? .

The reason for the opposing terms is the following theorem:

2.8  A few harder problems to think about

Problem 2A. Let M = (M,d) be a metric space. Show that

is itself a continuous function (where M × M is equipped with the product metric).

Part II
Basic Abstract Algebra

3  Homomorphisms and quotient groups

3.1  Generators and group presentations

Prototypical example for this section: D_2n =

Let G be a group. Recall that for some element x ∈ G, we could consider the subgroup

of G. Here’s a more pictorial version of what we did: put x in a box, seal it tightly, and shake vigorously. Using just the element x, we get a pretty explosion that produces the subgroup above.

What happens if we put two elements x, y in the box? Among the elements that get produced are things like

Essentially, I can create any finite product of x, y, x−1, y−1. This leads us to define:

This gives us an idea for a way to try and express groups compactly. Why not just write down a list of generators for the groups? For example, we could write

meaning that ℤ is just the group generated by one element.

There’s one issue: the generators usually satisfy certain properties. For example, consider ℤ∕100ℤ. It’s also generated by a single element x, but this x has the additional property that x¹⁰⁰ = 1. This motivates us to write

I’m sure you can see where this is going. All we have to do is specify a set of generators and relations between the generators, and say that two elements are equal if and only if you can get from one to the other using relations. Such an expression is appropriately called a group presentation.

Example 3.1.4 (Dihedral group)
The dihedral group of order 2n has a presentation

Thus each element of D_2n can be written uniquely in the form r^α or sr^α, where α = 0,1,…,n − 1.

Example 3.1.5 (Klein four group)
The Klein four group, isomorphic to ℤ∕2ℤ×ℤ∕2ℤ, is given by the presentation

Example 3.1.6 (Free group)
The free group on n elements is the group whose presentation has n generators and no relations at all. It is denoted F_n, so

In other words, F₂ = is the set of strings formed by appending finitely many copies of a, b, a−1, b−1 together.

Presentations are nice because they provide a compact way to write down groups. They do have some shortcomings, though.¹

Example 3.1.9 (Presentations can look very different)
The same group can have very different presentations. For instance consider

(To see why this is equivalent, set x = s, y = rs.)

3.2  Homomorphisms

Prototypical example for this section: The “mod out by 100” map, ℤ → ℤ∕100ℤ.

How can groups talk to each other?

Two groups are “the same” if we can write an isomorphism between them. And as we saw, two metric spaces are “the same” if we can write a homeomorphism between them. But what’s the group analogy of a continuous map? We simply drop the “bijection” condition.

Definition 3.2.1. Let G = (G,⋆) and H = (H,∗) be groups. A group homomorphism is a map ϕ : G → H such that for any g₁,g₂ ∈ G we have

(Not to be confused with “homeomorphism” from last chapter: note the spelling.)

The last two examples illustrate something: suppose we have a presentation of G. To specify a homomorphism G → H, we only have to specify where each generator of G goes, in such a way that the relations are all satisfied.

Important remark: the right way to think about an isomorphism is as a “bijective homomorphism”. To be explicit,

So the definitions of homeomorphism of metric spaces and isomorphism of groups are not too different.

Some obvious properties of homomorphisms follow.

Now let me define a very important property of a homomorphism.

Definition 3.2.5. The kernel of a homomorphism ϕ: G → H is defined by

It is a subgroup of G (in particular, 1_G ∈ kerϕ for obvious reasons).

We also have the following important fact, which we also encourage the reader to verify.

To make this concrete, let’s compute the kernel of each of our examples.

3.3  Cosets and modding out

Prototypical example for this section: Modding out by n: ℤ∕(n ⋅ ℤ)ℤ∕nℤ.

The next few sections are a bit dense. If this exposition doesn’t work for you, try [?].

Let G and Q be groups, and suppose there exists a surjective homomorphism

In other words, if ϕ is injective then ϕ : G → Q is a bijection, and hence an isomorphism. But suppose we’re not so lucky and kerϕ is bigger than just {1_G}. What is the correct interpretation of a more general homomorphism?

Let’s look at the special case where ϕ : ℤ → ℤ∕100ℤ is “modding out by 100”. We already saw that the kernel of this map is

Recall now that kerϕ is a subgroup of G. What this means is that ϕ is indifferent to the subgroup 100ℤ of ℤ:

So ℤ∕100ℤ is what we get when we “mod out by 100”. Cool.

In other words, let G be a group and ϕ : G ↠ Q be a surjective homomorphism with kernel N ⊆ G.

To formalize this, we will define a so-called quotient group G∕N in terms of G and N only (without referencing Q) which will be naturally isomorphic to Q.

For motivation, let’s give a concrete description of Q using just ϕ and G. Continuing our previous example, let N = 100ℤ be our subgroup of G. Consider the sets

N	=
1 + N	=
2 + N	=
99 + N	= .

The elements of each set all have the same image when we apply ϕ, and moreover any two elements in different sets have different images. Then the main idea is to notice that

Thus, given ϕ we define an equivalence relation ∼_N on G by saying x ∼_Ny for ϕ(x) = ϕ(y). This ∼_N divides G into several equivalence classes in G which are in obvious bijection with Q, as above. Now we claim that we can write these equivalence classes very explicitly.

Exercise 3.3.1. Show that x ∼ _Ny if and only if x = yn for some n ∈ N (in the mod 100 example, this means they “differ by some multiple of 100”). Thus for any g ∈ G, the equivalence class of ∼_N which contains g is given explicitly by

Here’s the word that describes the types of sets we’re running into now.

Remark 3.3.3 — Although the notation might not suggest it, keep in mind that g₁N is often equal to g₂N even if g₁≠g₂. In the “mod 100” example, 3 + N = 103 + N. In other words, these cosets are sets.

This means that if I write “let gH be a coset” without telling you what g is, you can’t figure out which g I chose from just the coset itself. If you don’t believe me, here’s an example of what I mean:

There’s no reason to think I picked x = 3. (I actually picked x = −13597.)

So, long story short,

In practice, people often still prefer to picture elements of Q as single points (for example it’s easier to think of ℤ∕2ℤ as {0,1} rather than {…,−2,0,2,…},{…,−1,1,3,…}). If you like this picture, then you might then draw G as a bunch of equally tall fibers (the cosets), which are then “collapsed” onto Q.

Now that we’ve done this, we can give an intrinsic definition for the quotient group we alluded to earlier.